package com.le.basic.subArrayProblem;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个数组arr，全是正数；一个整数aim，求累加和等 于aim的，最长子数组，
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 * 思路：
 * 因为全是正数，因此具有单调性，可以用滑动窗口解决
 */
public class Code_03_LongestSumSubArrayButAllPositive {

    public static int process(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int len = 0;
        int left = 0;
        int right = 0;
        int sum = arr[0];
        while (right < arr.length) {
            if (sum == aim) {
                len = Math.max(len, right - left + 1);
                sum -= arr[left++];
            } else if (sum < aim) {
                // right 右移
                if (++right == arr.length) {
                    break;
                }
                sum += arr[right];
            } else {
                sum -= arr[left++];
            }
        }
        return len;
    }

    // 思路一, 用哈希,空间复杂度O(n)
    public static int process1(int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int len = 0;
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (map.containsKey(sum - aim)) {
                len = Math.max(i - map.get(sum - aim), len);
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return len;
    }

    public static int[] generateArray(int num) {
        int[] arr = new int[num];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 10) + 1;
        }
        return arr;
    }

    @Test
    public void test1() {
        System.out.println("nice");
        for (int i = 0; i < 5 * 100 * 1000; i++) {
            int[] arr = generateArray(10);
            if (process1(arr, 10) != process(arr, 10)) {
                System.out.println(Arrays.toString(arr));
                System.out.println("no");
                break;
            }
        }

    }
}

